/*
 * Constructor a tree from a file.
=====
2 $ 7
0 1 2
8 12 16
1 3 4
4 5 6
=====
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
using namespace std;

typedef struct _tree_t {
    int value;
    struct _tree_t *parent;
    struct _tree_t *left;
    struct _tree_t *right;
} tree_t;

tree_t *new_tree(int v)
{
    tree_t *t = (tree_t *)malloc(sizeof(tree_t));
    memset(t, 0, sizeof(tree_t));
    t->value = v;
    return t;
}

/* This works only when parent appears before children nodes. */
tree_t *construct_tree(istream &is)
{
    string s[3];
    map<int, tree_t *> children_map;
    tree_t *root = NULL;
    while (is) {
        is >> s[0] >> s[1] >> s[2];
        if (s[0] != "$") {
            int p = atoi(s[0].c_str());
            tree_t *ptree;
            map<int, tree_t *>::const_iterator find = children_map.find(p);
            if (find != children_map.end()) {
                ptree = find->second;
            } else {
                ptree = new_tree(p);
            }
            tree_t *l = (s[1] == "$") ? NULL : new_tree(atoi(s[1].c_str()));
            tree_t *r = (s[2] == "$") ? NULL : new_tree(atoi(s[2].c_str()));
            ptree->left = l;
            ptree->right = r;
            if (l) {
                children_map[l->value] = l;
            }
            if (r) {
                children_map[r->value] = r;
            }
            if (!root) {
                /* XXX: There may be multiple trees, just select the first one. */
                root = ptree;
            }
        }
    }
    return root;
}

/* This works even when parent appears before children nodes. */
vector<tree_t *> construct_tree2(istream &is)
{
    string s[3];
    map<int, tree_t *> parent_map;
    /* adding */
    while (is) {
        is >> s[0] >> s[1] >> s[2];
        if (s[0] != "$") {
            tree_t *p = new_tree(atoi(s[0].c_str()));
            parent_map[p->value] = p;
            tree_t *l = (s[1] == "$") ? NULL : new_tree(atoi(s[1].c_str()));
            tree_t *r = (s[2] == "$") ? NULL : new_tree(atoi(s[2].c_str()));
            p->left = l;
            p->right = r;
            if (l) {
                l->parent = p;
            }
            if (r) {
                r->parent = p;
            }
        }
    }
    /* matching */
    for (map<int, tree_t *>::const_iterator it = parent_map.begin(); it != parent_map.end(); ++it) {
        tree_t *p = it->second;
        if (p->left) {
            map<int, tree_t *>::const_iterator it2 = parent_map.find(p->left->value);
            if (it2 != parent_map.end()) {
                free(p->left);
                p->left = it2->second;
                it2->second->parent = p;
            }
        }
        if (p->right) {
            map<int, tree_t *>::const_iterator it2 = parent_map.find(p->right->value);
            if (it2 != parent_map.end()) {
                free(p->right);
                p->right = it2->second;
                it2->second->parent = p;
            }
        }
    }
    /* find all roots */
    vector<tree_t *> roots;
    for (map<int, tree_t *>::const_iterator it = parent_map.begin(); it != parent_map.end(); ++it) {
        if (!it->second->parent) {
            roots.push_back(it->second);
        }
    }
    return roots;
}

void print_and_free(tree_t *root)
{
    if (!root) {
        return;
    }
    print_and_free(root->left);
    print_and_free(root->right);
    printf("%d ", root->value);
    free(root);
}

int main(int argc, char *argv[])
{
    vector<tree_t *> trees;
    if (argc == 1) {
        stringstream ss;
        std::string s;
        fstream file(__FILE__);
        int flag = 0;
        while (getline(file, s)) {
            if (s == "=====") {
                flag++;
                continue;
            }
            if (flag == 1) {
                ss << s << "\n";
            }
            if (flag == 2) {
                break;
            }
        }
        trees = construct_tree2(ss);
    } else {
        fstream file(argv[1]);
        trees = construct_tree2(file);
    }
    printf("%d trees in all:\n", trees.size());
    for (vector<tree_t *>::const_iterator it = trees.begin(); it != trees.end(); ++it) {
        print_and_free(*it);
        printf("\n");
    }
    return 0;
}
